package Leetcode.网格图;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @Author: kirito
 * @Date: 2024/5/6 12:08
 * @Description:
 * 迷宫中离入口最近的出口
 * 已解答
 * 中等
 * 相关标签
 * 相关企业
 * 提示
 * 给你一个 m x n 的迷宫矩阵 maze （下标从 0 开始），矩阵中有空格子（用 '.' 表示）和墙（用 '+' 表示）。同时给你迷宫的入口 entrance ，用 entrance = [entrancerow, entrancecol] 表示你一开始所在格子的行和列。
 *
 * 每一步操作，你可以往 上，下，左 或者 右 移动一个格子。你不能进入墙所在的格子，你也不能离开迷宫。你的目标是找到离 entrance 最近 的出口。出口 的含义是 maze 边界 上的 空格子。entrance 格子 不算 出口。
 *
 * 请你返回从 entrance 到最近出口的最短路径的 步数 ，如果不存在这样的路径，请你返回 -1 。
 *
 *
 *
 * 示例 1：
 *
 *
 * 输入：maze = [["+","+",".","+"],[".",".",".","+"],["+","+","+","."]], entrance = [1,2]
 * 输出：1
 * 解释：总共有 3 个出口，分别位于 (1,0)，(0,2) 和 (2,3) 。
 * 一开始，你在入口格子 (1,2) 处。
 * - 你可以往左移动 2 步到达 (1,0) 。
 * - 你可以往上移动 1 步到达 (0,2) 。
 * 从入口处没法到达 (2,3) 。
 * 所以，最近的出口是 (0,2) ，距离为 1 步。
 * 示例 2：
 *
 *
 * 输入：maze = [["+","+","+"],[".",".","."],["+","+","+"]], entrance = [1,0]
 * 输出：2
 * 解释：迷宫中只有 1 个出口，在 (1,2) 处。
 * (1,0) 不算出口，因为它是入口格子。
 * 初始时，你在入口与格子 (1,0) 处。
 * - 你可以往右移动 2 步到达 (1,2) 处。
 * 所以，最近的出口为 (1,2) ，距离为 2 步。
 * 示例 3：
 *
 *
 * 输入：maze = [[".","+"]], entrance = [0,0]
 * 输出：-1
 * 解释：这个迷宫中没有出口。
 *
 *
 * 提示：
 *
 * maze.length == m
 * maze[i].length == n
 * 1 <= m, n <= 100
 * maze[i][j] 要么是 '.' ，要么是 '+' 。
 * entrance.length == 2
 * 0 <= entrancerow < m
 * 0 <= entrancecol < n
 * entrance 一定是空格子。
 */

public class nearestExit {
    public static void main(String[] args) {
        char[][] arr = {{'.','+'}}	;
        int[] en = {0, 0};
        System.out.println(new nearestExit().nearestExit(arr, en));
    }
    private int ans = Integer.MAX_VALUE;
    public int nearestExit(char[][] maze, int[] entrance) {
        int m = entrance[0], n = entrance[1];
        search(maze, m, n, 0);
        return ans >= (m - 1) * (n - 1) ? -1 : ans;
    }

    private void search(char[][] maze, int row, int col, int path) {
        //墙壁或者已经走过就不能再走
        if (maze[row][col] != '.') {
            return;
        }
        if (row == 0
        || row == maze.length - 1
        || col == 0
        || col == maze[0].length - 1) {
            if (path != 0) {
                ans = Math.min(path, ans);
                return;
            }
        }

        maze[row][col] = '+';
        search(maze, Math.max(row - 1, 0), col, path + 1);
        search(maze, Math.min(row + 1, maze.length - 1), col, path + 1);
        search(maze, row, Math.max(col - 1, 0), path + 1);
        search(maze, row, Math.min(col + 1, maze[0].length - 1), path + 1);

    }

    public int nearestExit2(char[][] maze, int[] entrance) {
        int m = maze.length;
        int n = maze[0].length;
        Queue<int[]> bfs = new LinkedList<int[]>();
        int steps = -1;

        int x = entrance[0];
        int y = entrance[1];
        bfs.offer(new int[]{x,y,-1});
        maze[x][y] = '+';

        while(!bfs.isEmpty()){
            int[] p = bfs.poll();
            steps = p[2] + 1;
            x = p[0];
            y = p[1];

            //在边缘且不是起点
            if((x==0 || y==0 || x==m-1 || y==n-1) && steps > 0) return steps;

            //up
            if(x+1<m && maze[x+1][y] == '.'){
                bfs.offer(new int[]{x+1, y,steps});
                maze[x+1][y] = '+';
            }
            //down
            if(x-1>=0 && maze[x-1][y] == '.'){
                bfs.offer(new int[]{x-1, y,steps});
                maze[x-1][y] = '+';
            }
            //right
            if(y+1<n && maze[x][y+1] == '.'){
                bfs.offer(new int[]{x, y+1,steps});
                maze[x][y+1] = '+';
            }
            //left
            if(y-1>=0 && maze[x][y-1] == '.'){
                bfs.offer(new int[]{x, y-1,steps});
                maze[x][y-1] = '+';
            }
        }

        return -1;
    }

}
